\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{双链表的设计和实现}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle


\section{项目设计思路}

The purpose of using DoubleLinkedList is to solve the problem of accessing direct precursor and successor in the linked list. The purpose of setting the precursor and successor in the linked list. 

Since the List class will be implemented as a doubly linked list, we will need to maintain pointers to both ends of the list.

In considering the design, we will need to provide four classes:

1. The \verb|List| class itself, which contains links to both ends, the size of the list, and a host of methods.

2.The \verb|Node| class, which is likely to be a private nested class. A node contains the data and pointers to the previous and next nodes, along with appropriate constructors.

3.The \verb|const_iterator| class, which abstrats the notion of a position, and is a public nested class. The \verb|const_iterator| stores a pointer to "current" node, and provides implementation of the basic iterator operations, all in the form of overloaded operators such as \verb|=|, \verb|==|, \verb|!=|, and \verb|++|.

4.The \verb|iterator| class,which abstracts the notion of a position, and is a public nested class. THe \verb|iterator| has the same functionality as \verb|const_iterator|, except that \verb|operator*| returns a reference to theitem being viewed, rather than a constant reference to the item. An important technical issue is that an \verb|iterator| can be used in any routine that requires a \verb|const_iterato|, but not vice versa. In other words, \verb|iterator| IS-A \verb|const_iterator|.




\section{测试说明}
\verb|DoubleLinkedList<DT>::iterator find(DoubleLinkedList<DT>& _list, DT&  _val)| : self-designed external functions. The function is to find values \verb|_val| in your linked list \verb|_list|, if found, returns the value of the iterator for that node, if not, returns the value of the iterator for the \verb|tail node|.

\begin{verbatim}
template <typename DT>
typename DoubleLinkedList<DT>::iterator
find(DoubleLinkedList<DT>& _list, DT&  _val){
        if( _list.empty())
                return _list.end();
        else{
                 for(typename DoubleLinkedList<DT>::iterator p = _list.begin(); p !=  _list.end(); ++p ){
                        if ( *p  == _val){
                                return p;
                        }
                }

        }
        return _list.end();
}
\end{verbatim}

\verb|void printlist(const DoubleLinkedList<DT> &L )| : output list.

\begin{verbatim}
template <typename DT>
void printlist(const DoubleLinkedList<DT> &L ){
        if(L.empty())
                cout << "(empty)";
        else{
                auto itr = begin( L );
                cout << "[ " << *itr++;
                while( itr != end( L ) )
                        cout << "," << *itr++;
                cout << " ]" << endl;
        }
}

\end{verbatim}

\verb|int main(int argc, char *argv[])| : the main function.

\begin{verbatim}
int main(int argc, char *argv[]){
        \\Create a list L
	DoubleLinkedList<int> L;
	\\Use push_back to insert 1, 2, 3, 4, 5, 6
        for( int i = 1; i < 6; i ++ ){
                L.push_back(i);
        }
	\\Out L
        printlist( L );

        DoubleLinkedList<int>::iterator iter;
        int x = 3;
        iter = find(L, x);
        L.erase(iter);
        printlist( L );

        iter = find(L, x);
        return 0;
}

\end{verbatim}

The output:

[ 1,2,3,4,5 ]

[ 1,2,4,5 ]

Memory leak checking:

==3379== Memcheck, a memory error detector

==3379== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.

==3379== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info

==3379== Command: ./main

==3379==

[ 1,2,3,4,5 ]

[ 1,2,4,5 ]

==3379==

==3379== HEAP SUMMARY:

==3379==     in use at exit: 0 bytes in 0 blocks

==3379==   total heap usage: 9 allocs, 9 frees, 73,896 bytes allocated

==3379==

==3379== All heap blocks were freed -- no leaks are possible

==3379==

==3379== For counts of detected and suppressed errors, rerun with: -v

==3379== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

\end{document}
